package ee.homework.third;

public class HeapSort {

	private int heapSize;

	public void printList(int[] list) {
		for (int i = 0; i < list.length; i++) {
			System.out.print(list[i] + "  ");
		}
		System.out.println();
	}

	public void maxHeapify(int[] heapArray, int i) {
		int l = 2 * i + 1;
		int r = 2 * i + 2;
		int largest;
		if (l < heapSize && heapArray[l] > heapArray[i]) {
			largest = l;
		} else {
			largest = i;
		}
		if (r < heapSize && heapArray[r] > heapArray[largest]) {
			largest = r;
		}
		if (largest != i) {
			int tmp = heapArray[i];
			heapArray[i] = heapArray[largest];
			heapArray[largest] = tmp;
			maxHeapify(heapArray, largest);
		}
	}

	public void buildMaxHeap(int[] array) {
		heapSize = array.length;
		int lastParent = (heapSize - 1) / 2;
		for (int i = lastParent; i >= 0; i--) {
			maxHeapify(array, i);
		}
	}

	public void sort(int[] array) {
		buildMaxHeap(array);
		for (int i = array.length - 1; i > 0; i--) {
			int tmp = array[0];
			array[0] = array[i];
			array[i] = tmp;
			heapSize--;
			maxHeapify(array, 0);
		}
	}
}
